package com.aqie.medium.backtrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 89 格雷编码
 * n位二进制非负整数，两个连续数值仅有一个位数差异
 */
public class GrayCode {
    /*  1, 镜像法，动态规划  2ms  O(2^n)
        设n阶格雷码集合为G(n)，则G(n+1)阶格雷码为：
        给G(n)阶格雷码每个元素二进制形式前面添加0；、
        设G(n)集合的倒序（镜像）为R(n)，给R(n)每个元素二进制形式前面添加1；
        G(n+1) = G(n) + R(n)拼接两个集合即可得到下一阶格雷码
     */
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<Integer>() {{ add(0); }};
        for (int i = 0; i < n; i++) {
            int head = 1 << i;
            // 倒序遍历，并且加上一个值添加到结果中
            for (int j = res.size() - 1; j >= 0; j--)
                res.add(head + res.get(j));
        }
        return res;
    }

    /**
     * 2， 维基百科 生成gray O(N2^N)
     * 以二进制为 0 值的格雷码为第零项，第一项改变最右边的位元，第二项改变右起第一个为1的位元的左边位元，第三、四项方法同第一、二项，如此反复，即可排列出n个位元的格雷码。
     *
     * @param n
     * @return
     */
    public List<Integer> grayCode2(int n) {
        List<Integer> gray = new ArrayList<Integer>();
        gray.add(0); //初始化第零项
        for (int i = 1; i < 1 << n; i++) {
            //得到上一个的值
            int previous = gray.get(i - 1);
            //同第一项的情况
            if (i % 2 == 1) {
                previous ^= 1; //和 0000001 做异或，使得最右边一位取反
                gray.add(previous);
                //同第二项的情况
            } else {
                int temp = previous;
                //寻找右边起第第一个为 1 的位元
                for (int j = 0; j < n; j++) {
                    if ((temp & 1) == 1) {
                        //和 00001000000 类似这样的数做异或，使得相应位取反
                        previous = previous ^ (1 << (j + 1));
                        gray.add(previous);
                        break;
                    }
                    temp = temp >> 1;
                }
            }
        }
        return gray;
    }

    /**
     * 3, 二进制转 gray码公式 O(2^n)
     */
    public List<Integer> grayCode3(int n) {
        List<Integer> gray = new ArrayList<Integer>();
        for(int binary = 0;binary < 1 << n; binary++){
            gray.add(binary ^ binary >> 1);
        }
        return gray;
    }

    /**
     * 4. 查找表 1ms
     */
    public static List<Integer> grayCode4(int n) {
        int table[] = {0, 1, 3, 2, 6, 7, 5, 4, 4, 5, 7, 6, 2, 3, 1, 0};
        int total = (int)Math.pow(2, n);
        List<Integer> res = Arrays.asList(new Integer[total]);
        for (int i = 0; i < total; i++){
            int num = i;
            int gray = 0;
            int factor = 1;
            while(num != 0){
                int local = num % 16;
                gray += table[local] * factor;
                factor *= 8;
                num /= 8;
            }
            res.set(i, gray);
        }
        return res;
    }

    public static void main(String[] args) {
      System.out.println(grayCode4(2));
    }

}
